上集解答

第一個是O(N)、第二個是O(N²)，不知道大家有沒有答對呢～

貪婪演算法Greedy

貪婪演算法是一種非常常見的演算法，在生活中說不定大家也很直覺的在利用了。

簡單來說，貪婪是「在每一步都選擇最佳解，期望結果或是最佳解」，比如今天你要去一個地方，有很多條路，你可以選擇分成很多步，每一步都選擇最短的走。

貪婪在有最佳子結構的問題中最為有效。（最佳子結構的意思是局部最佳解能決定全域最佳解。簡單地說，問題能夠分解成子問題來解決，子問題的最佳解能遞推到最終問題的最佳解。）

不過如果今天他不是有最佳子結構的題目，貪婪通常不能真的得到最好的解答。

範例題目

題目敘述

有一個金額N，我們希望用1、5、10、50的硬幣來湊齊他。

解題思路

其實這題是有最佳子結構的（用金額較大的硬幣，一定比用小硬幣湊的硬幣少），所以我們可以來思考貪婪怎麼實現。

比如其實我們可以每次都拿當前最大的硬幣，直到湊齊金額。

fun main(){
    var n = readln().toInt()
    var ans = 0
    while(n>=50){
        n-=50;
        ans+=1;
    }
    while(n>=10){
        n-=10;
        ans+=1;
    }
    while(n>=5){
        n-=5;
        ans+=1;
    }
    while(n>=1){
        n-=1;
        ans+=1;
    }
    println("$ans")
}

不過只有在今天是1、5、10、50才會成立喔，比如今天是1、5、10、12、20之類的，可能就不能使用貪婪演算法了，因為他不滿足剛剛提出的條件。

課堂練習～

假設你是一位很棒的家長，想要給你的孩子們一些小餅乾。

但是，每個孩子最多隻能給一塊餅乾。對每個孩子i，都有一個胃口值gᵢ（必為正），這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅乾j，都有一個尺寸sⱼ。如果sⱼ>=gᵢ，我們可以將這個餅乾j
分配給孩子i，這個孩子會得到滿足。你的目標是儘可能滿足越多數量的孩子，並輸出你滿足了多少小孩。（一個小朋友最多只能擁有一塊餅乾）

輸入說明

第一行一個正整數n代表用幾個小孩

接下來一行有n個數字，分別代表小孩的胃口值（必定遞增排列）

第一行一格m代表有幾個餅乾

接下來一行有n個餅乾，分別代表餅乾的尺寸（必定遞增排列）

n必定小於<m

輸出說明

輸出一個值，代表有多少小孩快樂的吃到了餅乾。

輸入範例

5

1 2 3 4 5

8

2 2 3 3 9 11 13 17

輸出範例

5